/*
 * One example for NOI CSP-J Lesson 10:
 * <https://courses.fmsoft.cn/plzs/noijunior-csp-exercises-lower.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cassert>

using namespace std;

using llong_t = long long;
using adj_list = vector<vector<pair<int, int>>>;

struct stop_info {
    llong_t t_begin, distance;
    int vertex;
    // 优先级队列使用 < 运算符执行对比，默认行为是大者冒顶
    bool operator < (const stop_info &x) const {
        return t_begin + distance > x.t_begin + x.distance;
    }
};

// 从给定的起始顶点处执行 BFS
llong_t bfs(adj_list& graph, int start, int stop, int k)
{
    llong_t ans = -1;

    // 创建优先级队列用于跟踪遍历过程
    priority_queue<stop_info> pq;

    // 标记起始节点被访问并排入队列
    pq.push({0, 0, start});

    // 到达每个顶点的时间对 k 取模，则只有 k 种情形：[0, k - 1]
    vector<vector<llong_t>> visited(graph.size(), vector<llong_t>(k, LLONG_MAX));

    // 标记已访问。
    visited[start][0] = 0;

    // 若优先级队列未空就继续循环
    while (!pq.empty()) {

        auto min_stop = pq.top();
        pq.pop();

        if (min_stop.vertex == stop && min_stop.distance % k == 0) {
            ans = min_stop.t_begin + min_stop.distance;
            break;
        }

        // 处理出队顶点的所有邻接顶点。
        // 注意并未处理有环的情形（也就是未记录顶点是否被访问过）
        for (auto x : graph[min_stop.vertex]) {
            int v = x.first;
            int time_open = x.second;

            llong_t time_reach = min_stop.t_begin + min_stop.distance;

            int mod = (min_stop.distance + 1) % k;
            if (visited[v][mod] <= min_stop.t_begin)
                continue;                           // 有环且重复了
            visited[v][mod] = min_stop.t_begin;     // 标记被访问

            if (time_reach >= time_open) {
                pq.push({min_stop.t_begin, min_stop.distance+1, v});
            }
            else {
                // 调整出发时间。
                int time_inc = ((time_open - time_reach + k - 1)/k) * k;
                pq.push({min_stop.t_begin + time_inc, min_stop.distance+1, v});
            }
        }
    }

    return ans;
}

int main()
{
    adj_list graph(5 + 1);
    graph[1].push_back({2, 0});
    graph[2].push_back({5, 1});
    graph[1].push_back({3, 0});
    graph[3].push_back({4, 3});
    graph[4].push_back({5, 1});

    int ans;
    ans = bfs(graph, 1, 5, 3);
    assert(ans == 6);

    int n, m, k;
    cin >> n >> m >> k;
    adj_list graph2(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, a;
        cin >> u >> v >> a;
        graph2[u].push_back({v, a});
    }

    ans = bfs(graph2, 1, n, k);
    cout << ans << endl;
    return 0;
}

